Many computer systems dynamically allocate memory to a task. The following is a somewhat simplified explanation of a method for dynamic memory allocation and garbage collection.
Referring to FIG. 1, in a typical multitasking computer system 20 each active task is assigned a portion 24 of the computer's memory space 22. The memory space 24 assigned to a task can be divided into three regions: one region 26 for holding the code which represents and controls the task, another region 28 that contains a set of "root" pointers used by the task, and a third region 30, called the heap, which is used for dynamic memory allocation.
It should be understood that FIG. 1 represents only one of many ways in which memory may be allocated for storing the roots, code and heap associated with a task or a set of tasks.
When the task associated with the heap 30 needs space for storing an array or other program "object", it requests and is allocated a block of memory 32 in the heap 30. Additional requests for memory will result in the allocation of memory blocks 34, 36, 38, 40 and so on. Clearly, if the task continues to ask for more memory, all the space in the heap 30 will eventually be used and the task will fail for lack of memory. Therefore space must be restored by either explicit actions of the program, or some other mechanism.
It is well known that most tasks "abandon" much of the memory space that is allocated to them. Typically, the task stores many program objects in allocated memory blocks, and discards all pointers to many of those objects after it has finished processing them because it will never need to access those objects again. An object for which there are no pointers is often termed an "inaccessible object", and the memory space it occupies is "inaccessible" to the task which once used it. For instance, in FIG. 1 the accessible objects on the left half of heap 30 are shaded, and the inaccessible objects are not shaded.
The solution to this problem is to recover blocks of memory space in the heap 30 which are no longer being used by the task. Garbage collection is the term used to refer to automatic methods of recovering unused memory in the heap 30. Garbage collectors generally gather and recover unused memory upon the occurrence of a certain amount of memory usage, most typically when half of the storage space in the heap 30 has been allocated.
Thus, the purpose of garbage collection is to recover unused or abandoned portions of memory in a heap 30 so that the task using the heap 30 will not run out of memory.
For the most part, there are two primary prior art garbage collection techniques. One is called Stop and Copy, and the other is herein called Mark and Sweep.